import heapq
from typing import List

class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.maxHeapSize = k
        self.heapSize = 0
        if len(nums) >= k:
            self.__kheap(nums)
        else:
            self.heap = nums
            self.heapSize = len(nums)
            heapq.heapify(self.heap)

    def __kheap(self, nums: List[int]):
        self.heap = []
        for num in nums:
            if self.heapSize < self.maxHeapSize:
                heapq.heappush(self.heap, num)
                self.heapSize = self.heapSize + 1
            else:
                minElement = self.heap[0]
                if minElement <= num:
                    heapq.heappop(self.heap)
                    heapq.heappush(self.heap, num)

    def add(self, val: int) -> int:
        if self.heapSize < self.maxHeapSize:
            heapq.heappush(self.heap, val)
            self.heapSize = self.heapSize + 1
            return self.heap[0]
        else:
            minElement = self.heap[0]
            if minElement > val:
                return minElement
            else:
                heapq.heappop(self.heap)
                heapq.heappush(self.heap, val)
                return self.heap[0]


# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)

kthLargest = KthLargest(3, [4,5,8,2])
print("{0} == 4".format(kthLargest.add(3)))
print("{0} == 5".format(kthLargest.add(5)))
print("{0} == 5".format(kthLargest.add(10)))
print("{0} == 8".format(kthLargest.add(9)))
print("{0} == 8".format(kthLargest.add(4)))

print("another example:")

# ["KthLargest","add","add","add","add","add","add","add","add","add","add","add","add","add","add","add","add","add","add","add","add","add","add","add","add","add","add","add"]
# [[7,],[3],[2],[3],[1],[2],[4],[5],[5],[6],[7],[7],[8],[2],[3],[1],[1],[1],[10],[11],[5],[6],[2],[4],[7],[8],[5],[6]]

kthLargest = KthLargest(7, [-10,1,3,1,4,10,3,9,4,5,1])
print("heap size: {0}".format(kthLargest.heapSize))
print("heap: {0}".format(kthLargest.heap))
print("{0} == 3".format(kthLargest.add(3)))